Euler Problem 77

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?



In [1]:

    
from sympy import sieve

N = 200
s = [0]*N
s[0] = 1
for p in sieve.primerange(1, N):
    for k in range(N-1, 0, -1):
        for i in range(k-p, -1, -p):
            s[k] += s[i]
for k in range(100):
    if s[k] > 5000:
        print(k, s[k])
        break



In [ ]: